package com.ys.ArrayList模拟;

/**
 * 描述: TODO
 *
 * @author CodeYang
 * @version 2020/12/25 9:07
 */
public class ArrayList<E> implements List<E> {
    /**
     * 定义一个容器，用于保存集合中的数据
     */
    private Object[] elementData;

    /**
     * 定义一个变量，用于保存实际添加元素的个数
     */
    private int size;

    /**
     * 无参构造方法，实例化elementData数组，并设置空间长度为10
     */
    public ArrayList() {
        this(10);
    }

    /**
     * 有参构造方法，实例化elementData数组，并设置指定的空间大小
     *
     * @param cap 数组的空间长度
     */
    public ArrayList(int cap) {
        // 处理cap的值为负数的情况
        if (cap < 0) {
            throw new IllegalArgumentException("参数不合法，cap:" + cap);
        }
        // 实例化elementData数组
        this.elementData = new Object[cap];
    }

    /**
     * 获得集合中实际存放元素的个数
     *
     * @return
     */
    public int size() {
        return this.size;
    }

    /**
     * 添加元素，在List末尾添加元素
     *
     * @param element 需要插入元素
     */
    @Override
    public void add(E element) {
        // 检查数组是否需要扩容
        ensureCapacityInternal();
        // 把元素添加到集合末尾，并更新size的值
        elementData[size++] = element;
    }

    /**
     * 插入元素，在指定索引位置插入元素
     *
     * @param index   需要插入的索引位置
     * @param element 需要插入元素
     */
    @Override
    public void add(int index, E element) {
        // 判断index是否合法，合法取值范围：[0, size]
        if (index < 0 || index > size) {
            throw new ArrayIndexOutOfBoundsException("数组索引越界异常，index:" + index);
        }
        // 检查数组是否需要扩容
        ensureCapacityInternal();
        // 把插入索引及其之后的元素往后挪动一位（挪动方向：从后往前）
       /* for (int i = size - 1; i >= index; i--) {
            // 把前一个元素完后挪动一位
            elementData[i + 1] = elementData[i];
        }*/
        // 上面的复制操作可以使用System.arraycopy() 来实现
        /**
         *  解析:
         *   把 数组 A copy 到 数组A 中去,
         *   把 数组A 中的 index - 结束的数组元素 覆盖到 "新"数组 开始位置为index+1 ,覆盖长度为[len = size -index]
         *   把 要插入的元素 放到 "新数组的"[index] 位置,覆盖掉原来的内容
         */
        System.arraycopy(elementData,index,elementData,index+1,size-index);
        // 在index位置执行赋值操作
        elementData[index] = element;
        // 执行size的递增操作
        size++;
    }

    /**
     * 根据索引删除数组元素
     *
     * @param index 删除元素的索引
     * @return 返回被删除的元素
     */
    @Override
    public E remove(int index) {
        // 判断index是否合法，合法取值范围：[0, size - 1]
        if (index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException("数组索引越界异常，index:" + index);
        }
        // 删除元素之前，我们先保存需要被删除的元素
        E oldValue = (E) elementData[index];
        // 把删除索引之后的元素往前挪动一位（挪动方向：从前往后）
        /*for (int i = index; i < size - 1; i++) {
            // 把后一个元素往前挪动一位
            elementData[i] = elementData[i + 1];
        }*/
        /**
         *  使用System.arrcopy() 来实现 删除元素:
         *  核心思想: 把目标元素的后面的内容整体前移
         *   1把 数组 A copy 到 数组A 中去,
         *   2把 数组A 中从 index+1 之后的元素内容 覆盖到 "新" 数组A 中 去, 从index开始,长度为: size -index -1 (挪动次数)
         *   size--;
         */
        System.arraycopy(elementData,index+1,elementData,index,size-index -1);

        // 更新size的值，也就是执行size的递减操作
        size--;
        // 回收掉 之前在size-1 地方的元素内容 让GC回收掉
        elementData[size] =null;
        // 返回被删除的元素
        return oldValue;
    }

    /**
     * @param element 需要删除的元素
     * @return 失败返回 false ,成功返回 true
     */
    @Override
    public boolean remove(E element) {
        if (null == element) {
            for (int i = 0; i < size; i++) {
                if (null == element) {
                    remove(i);
                    return true;
                }
            }
        } else {
            for (int i = 0; i < size; i++) {
                if (element.equals(elementData[i])) {
                    remove(i);
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 判断数组是否为空,之间判断 实际元素 ==0 即可
     * @return
     */
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 获得第一个匹配的元素索引
     * @param element 需要查找的元素
     * @return
     */
    @Override
    public int indexOf(E element) {
        // 判断查找元素是否为null 是null 返回null所在的序号
        if (null == element){
            for (int i = 0; i < size; i++) {
                if (null == elementData[i]){
                    return i;
                }
            }
        } else {
            for (int i = 0; i < size; i++) {
                if (element.equals(elementData[i])){
                    return i;
                }
            }
        }
        return -1;
    }

    /**
     * 根据索引获取元素
     *
     * @param index 获取元素的索引值
     * @return 返回index对应的元素值
     */
    @Override
    public E get(int index) {
        // 判断index是否合法，合法取值范围：[0, size - 1]
        if (index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException("数组索引越界异常，index:" + index);
        }
        // 返回index所对应的元素值
        return (E) elementData[index];
    }


    /**
     * 检查数组是否需要扩容
     */
    private void ensureCapacityInternal() {
        // 如果数组的空间长度和实际存放元素的个数相同，则需要扩容
        if (elementData.length == size) {
            // 创建一个比原数组空间长度更大的新数组，空间长度为：原数组的2倍+1
            Object[] copyArr = new Object[(size << 1) + 1];
            // 把elementData中的元素拷贝进入新数组
            System.arraycopy(elementData, 0, copyArr, 0, size);
            // 让elementData指向扩容之后的新数组
            elementData = copyArr;
        }
    }
}
